package cn.zjitc.algorithm.sort;

/**
 * 对数组a中的元素进行排序
 * @author dell
 */
public class Insertion {
    public static void sort(Comparable[] a) {
        for (int i = 1; i < a.length; i++) {
            //当前元素为a[i],依次和i前面的元素比较，找到一个小于等于a[i]的元素
            for (int j = i; j>0 ; j--) {
                //比较索引处j的值和索引处j-1的值，如果索引j-1处的值比索引j处的值大，则交换数据，如果不大，那么找到合适的位置，退出循环即可
                if (greater(a[j-1],a[j])){
                    //交换元素
                    exch(a,j-1,j);
                }else {
                    //找到了该元素，结束
                    break;
                }
            }
        }
    }


    private static void exch(Comparable[] a, int i, int j) {
        Comparable temp;
        temp=a[i];
        a[i]=a[j];
        a[j]=temp;
    }

    private static boolean greater(Comparable x, Comparable y) {
        return x.compareTo(y)>0;
    }
}
